Digital wireless communication systems are used to convey a variety of information between multiple locations. With digital communications, information is translated into a digital or binary form, referred to as bits, for communication purposes. The transmitter maps this bit stream into a modulated symbol stream, which is detected at the digital receiver and mapped back into bits and information.
In digital communications, the radio environment presents many difficulties that impede successful communications. One difficulty is that the signal level can fade because the signal may travel in multiple paths. As a result, signal images may arrive at the receiver antenna out of phase. This type of fading is commonly referred to as Rayleigh fading or fast fading. When the signal fades, the signal-to-noise ratio becomes lower, causing degradation in the quality of the communication link.
A second problem occurs when the multiple signal paths are much different in length. In this case, time dispersion occurs, in which multiple fading signal images arrive at the receiver antenna at different times, thus giving rise to signal echoes or rays. This causes intersymbol interference (ISI), where the echoes of one symbol interfere with subsequent symbols.
At the receiver, coherent demodulation is desirable, since it provides the best performance. This requires knowledge of the multipath channel. In many wireless applications, this channel is time-varying, due to transmitter motion, receiver motion, and/or scatterer motion. Thus, there is a need to track a time varying multipath channel.
To provide coherent demodulation of multipath signals, a maximum-likelihood-sequence-estimation (MLSE) equalizer may be employed. Such an equalizer considers various hypotheses for the transmitted symbol sequence, and with a model of the dispersive channel, determines which hypothesis best fits the received data. This is efficiently realized using the Viterbi algorithm. This equalization technique is well known to those skilled in the art, and can be found in J. C. Proakis, Digital Communications, 1989.
The conventional MLSE equalizer can be explained by a simple example. Suppose the transmitter transmits a symbol stream s(n), which takes on values “+B” or “−B” corresponding to bit values 0 or 1, respectively. This stream is modulated using binary-shift keying (BPSK). At the receiver, the received signal is filtered, amplified, and mixed down using the I and Q carriers, then sampled once every symbol period (T), giving a received signal stream r(n). In this example, the intervening channel consists of two rays, a main ray and an echo, where the echo arrives T seconds later and T is the symbol period. Then the received signal can be modeled asr(n)=c0s(n)+c1s(n−1)+η(n),  (1)where c0 and c1 are complex channel tap values and η(n) is additive noise or interference.
In the MLSE equalizer, at iteration n, there would be two different previous “states,” 0 and 1, corresponding to the two possible values for the previous symbols:
1. s(n−1)=B  Previous State=0
2. s(n−1)=−B  Previous State=1.
Associated with each previous state there would be an accumulated metric, accumulated from previous iterations, giving rise to accumulated metrics A0(n−1) and A1 (n−1) for previous state 0 and previous state 1, respectively.
There would also be two current states corresponding to two possible values for s(n). Each possible pairing of a previous state with a current state corresponds to a hypothetical sequence {sh(n−1), sh(n)}. For each of these hypotheses, there will be a corresponding hypothesized received signal value at time n:rh(n)=c0sh(n)+c1sh(n−1)  (2)Furthermore, for each of these hypotheses, there will be a corresponding “branch” metric given byMh(n)=|r(n)−rh(n)|2.  (3)
In the example, there are four possible hypothetical sequences which can be denoted by hε{00, 01, 10, 11}, as illustrated in Table 1.
TABLE 1Naming Convention for StatesPrevious StateCurrent Stateh0(B) 0(B) 001(−B)0(B) 100(B) 1(−B)011(−B)1(−B)11
The candidate metrics for each possible current state would be the sum of the corresponding-branch metrics and the previously accumulated metric associated with sh(n−1). For each current state, there are two possible previous states. For each current state, the previous state which gives the smallest candidate metric is selected as the predecessor state, and the candidate metric becomes the accumulated metric for that current state.
Thus, for current state 0 (i.e., s(n)=B), there will be two hypothetical sequences {sh(n−1)=B, sh(n)=B} or {sh(n−1)=−B, sh(n)=B}, denoted by hypotheses h=00 and h=10. This gives rise to two candidate metrics for current state 0:C00(n)=A0(n−1)+M00(n)  (4)C10(n)=A1(n−1)+M10(n).  (5)The smaller of these two candidate metrics gives the accumulated metric for current state 0. The corresponding previous state becomes the predecessor state to state 0 at time n:
1. If C10(n)<C00(n), A0(n)=C10(n)
2. If C00(n)<C10(n), A0(n)=C00(n)
A similar procedure is applied to current state 1 (i.e., s(n)=−B), in which case the two hypotheses are h=01 and h=11.
For each n, four hypothesized received signal values must be computed according to equation (2). Computing each hypothesized value rh(n) involves two multiplication operations. Each of these multiplication operations involves the product of one of the channel taps and a hypothetical symbol value.
If B is set to +1, the multiplications become simply sign changes. However, if amplitude modulation is used, this is not possible. Also, suppose symbol values can be normalized to
      {          ⅇ              j        ⁢                              2            ⁢                                                  ⁢            π                    8                ⁢        l              }        l    =    0    7(i.e., 8PSK modulation). In this case, the necessary multiplications can not be implemented as simple sign changes.
One way to increase the throughput over a digital channel is to allow each transmitted symbol to take on more than two values. In general, each symbol might be chosen from a set of M possible values {B1, B2, . . . , BM} thereby increasing the number of bits per symbol. The complexity of the conventional implementation of the MLSE equalizer increases exponentially with the number of allowed symbols (i.e., with M). Specifically, with “L” channel taps, the number of multiplications needed for the conventional implementation of the equalizer is proportional (proportionality constant greater than one) to ML-1.
Even with moderate values for M and L (e.g., 8 and 5 respectively), it is impractical to implement the equalizer in grand purpose DSPs with low power consumption. The trend in power sensitive applications is to move away from DSPs toward ASICs. ASICs can be optimized for performing one task with low power consumption and small size (i.e., small gate count). Implementing multipliers in an ASIC is much more expensive (in terms of power consumption and gate count) than implementing circuits for addition or subtraction. Therefore, it is highly desirable to avoid many of the multiplications associated with the conventional implementation of MLSE equalizers.
Because of the trend toward increasing the number of required multiplication operations and due to the fact that technology is moving away from DSPs, where multiplication operations are easy, toward ASICs, where multiplications are relatively expensive, it is desirable to reduce the number of multiplications actually performed by the MLSE.